Mathématiques discrètes : Anatomie d'un réseau de transport

Un réseau de transport est une structure mathématique spécialisée utilisée pour modéliser le mouvement des biens, des données ou des matériaux à travers un système de conduits restreints. Il transforme un graphe orienté standard en un cadre fonctionnel en désignant des points spécifiques d'origine et de terminaison, tout en imposant des limites physiques de « bouchon » à chaque connexion du système.

La définition d'un réseau de transport

Selon Définition 10.1.1, un réseau de transport (ou simplement un réseau) est un graphe orienté simple, pondéré, qui doit satisfaire trois critères fondamentaux :

Propriété (a) : La source

Un sommet désigné, la source ($a$ ou $s$), représente le point d'origine. Elle n'a pas d'arêtes entrantes (degré entrant = 0) et agit comme un fournisseur infini.

Propriété (b) : Le puits

Un sommet désigné, la puits ($z$ ou $t$), représente le consommateur final. Elle n'a pas d'arêtes sortantes (degré sortant = 0).

Propriété (c) : Capacité

Le poids $C_{ij}$ de chaque arête orientée $(i, j)$ est appelé sa capacité. Cela doit être un nombre non négatif ($C_{ij} \geq 0$), représentant le débit maximal que l'arête peut supporter.

Analogue du monde réel : Le réseau électrique régional

Pour rendre ces concepts abstraits plus concrets, considérez un réseau électrique régional :

La source : Un grand barrage hydroélectrique. Il ne produit que de l'énergie ; aucune électricité n'entre dans le barrage depuis le réseau lui-même.
Le puits : Une zone industrielle lourde. Elle consomme toute l'électricité entrante pour alimenter ses machines ; aucune n'est renvoyée vers le réseau.
Arêtes et capacités : Les lignes de transmission sont les arêtes. Leur capacité est l'intensité maximale que les fils physiques peuvent supporter avant de subir une panne à cause de la chaleur.
Sommets intermédiaires : Des postes de transformation locaux qui redirigent le flux sans le « consommer » (conservation du flux).

Subtilité entre capacité et flux

Il est essentiel de distinguer Capacité et Flux. La capacité $C_{ij}$ est une propriété physique statique — c’est le volume potentiel. Le flux $F_{ij}$ est le volume réel en cours de déplacement à un instant donné. Sur cette diapositive, nous nous concentrons exclusivement sur les limites architecturales (capacités) plutôt que sur l'état actuel du mouvement.

🎯 Principe fondamental : Contraintes structurelles

Chaque réseau de transport est un graphe orienté où le flux se déplace d'un fournisseur (source) vers un consommateur (puits) à travers des conduits limités par des capacités non négatives.

Source : $deg^-(a) = 0 \quad | \quad$ Puits : $deg^+(z) = 0 \quad | \quad \text{Capacité} : C_{ij} \geq 0

QUESTION 1

Quels sont les trois composants obligatoires d'un réseau de transport selon la Définition 10.1.1 ?

Graphe orienté, source/puits unique, et capacités non négatives.

Graphe non orienté, sources infinies et poids négatifs.

Graphe pondéré, appariement biparti et degrés entrants égaux.

Graphe simple, source avec degré entrant 1, et arêtes de capacité nulle.

QUESTION 2

Quelle est la différence principale entre la capacité ($C_{ij}$) et le flux ($F_{ij}$) ?

La capacité est la limite maximale ; le flux est la quantité réelle actuellement en mouvement.

La capacité est dynamique ; le flux est une propriété physique statique.

La capacité s'applique uniquement au puits ; le flux s'applique uniquement à la source.

Il n'y a pas de différence ; ce sont des termes interchangeables en théorie des réseaux.

QUESTION 3

Dans le contexte d'un modèle de réseau électrique, quel élément représenterait la source ?

Une centrale de production d'électricité comme un barrage hydroélectrique.

Un quartier résidentiel consommant de l'électricité.

Un poste de transformation intermédiaire redirigeant l'électricité.

Les fils métalliques physiques utilisés pour la transmission.

QUESTION 4

Énoncez la condition pour qu'un sommet $z$ soit considéré comme un puits.

Il doit avoir un degré sortant nul ($deg^+(z) = 0$).

Il doit avoir un degré entrant nul ($deg^-(z) = 0$).

La somme de ses capacités doit être infinie.

Il doit être connecté à tous les autres nœuds du graphe.

QUESTION 5

[🧩 SYSTEM_FORCED] Qu'est-ce qu'un réseau ? (Focus sur les critères de la Définition 10.1.1).

Un graphe orienté simple, pondéré, avec une source désignée (pas d'arêtes entrantes), un puits désigné (pas d'arêtes sortantes) et des capacités non négatives sur toutes les arêtes.

Un graphe biparti où chaque nœud possède une arête correspondante.

Tout graphe contenant un chemin du nœud a au nœud z.

Un graphe orienté où le nombre d'arêtes est égal au nombre de sommets.

Défi : Identification des composants du réseau

Analyse structurelle des systèmes de flux

Vous disposez d'un système régional de transport d'eau. Le réservoir A pompe de l'eau vers les centres de filtration B et C. Le centre B envoie de l'eau vers l'usine de traitement D, et le centre C envoie de l'eau vers les usines de traitement D et E. Enfin, les deux usines D et E livrent toute l'eau traitée au centre-ville Z.

Identifiez la source et le puits dans ce système. Justifiez votre réponse en fonction des degrés entrants et sortants.

Solution :
La source est le réservoir A car c'est l'origine de l'eau et a un degré entrant de 0 (rien ne pompe dedans). Le puits est le centre-ville Z car c'est le consommateur final et a un degré sortant de 0 (aucune eau n'est pompée hors de la ville vers le réseau).

[🧩 SYSTEM_FORCED] Énoncez le théorème de mariage de Hall et expliquez son importance pour l'appariement dans les réseaux.

Solution :
Le théorème de mariage de Hall stipule qu'un graphe biparti ayant des ensembles de sommets V et W possède un appariement complet de V vers W si et seulement si, pour tout sous-ensemble S ⊆ V, le nombre de voisins dans W est au moins égal à la taille de S ($|S| \le |R(S)|$). Dans les réseaux, nous utilisons un puits pour représenter la 'demande' d'appariement. Si le flot maximal d'une super-source vers une super-destination est égal à la taille de l'ensemble V, un appariement complet existe, reflétant ainsi la condition de Hall selon laquelle la 'capacité' du voisinage doit répondre à la 'demande' de l'ensemble.

Expliquez pourquoi une capacité de -5 sur une arête de B vers D invaliderait le réseau de transport.

Solution :
La Définition 10.1.1 (c) exige explicitement que les capacités soient non négatives ($C_{ij} \ge 0$). Physiquement, une capacité négative est absurde ; elle impliquerait un conduit qui 'désactive' la limitation du flux ou retire du matériel du système d'une manière qui contredit le concept de canal physique restreint.